﻿#pragma once

#include <iostream>
#include <assert.h>
#include <algorithm>

#include <thread>
#include <mutex>
#include <atomic>

#include <unordered_map>
#include <map>
#include <vector>

static const size_t MAX_BYTES = 256 * 1024; //每个线程单次申请的最大为256KB空间
static const size_t NFREELISTS = 208;       //自由链表的最大个数（哈希桶的最大容量）
static const size_t NPAGES = 129;           //PageCache桶的自由链表个数
static const size_t PAGE_SHIFT = 13;        //页大小转换偏移，即一页是2^13 = 8KB

//不同的平台下，内存不同，所以分成的页数量也不同，用不同的类型来标定页号
//在win32下，只有_WIN32定义
//在win64下，_WIN32 和_WIN64 都有定义
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
	#include <Windows.h>
#elif _WIN32
	typedef size_t PAGE_ID;
	#include <Windows.h>
#else
	// Linux
#endif

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif
	// Linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

//获取一个指针大小的指针
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理切分好的小对象的自由链表（每个FreeList对象都相当于一个定长的自由链表）
class FreeList
{
public:	
	void Push(void* obj)
	{
		assert(obj);
		//头插
		NextObj(obj) = _freelist_head;
		_freelist_head = obj;

		++_size;
	}
	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freelist_head;
		_freelist_head = start;

		/*int i = 0;
		void* cur = start;
		while (cur)
		{
			cur = NextObj(cur);
			++i;
		}
		if (i != n)
		{
			int x = 0;
		}*/

		_size += n;
	}
	void* Pop()
	{
		assert(_freelist_head);
		//头删
		void* obj = _freelist_head;
		_freelist_head = NextObj(obj);

		--_size;
		return obj;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freelist_head;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freelist_head = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}		

	bool Empty()
	{
		return _freelist_head == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}

private:
	void* _freelist_head = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 整体控制在最多10%左右的内碎⽚浪费
// [1,128]               8byte对⻬        freelist[0,16)
// [128+1,1024]          16byte对⻬       freelist[16,72)
// [1024+1,81024]        128byte对⻬      freelist[72,128)
// [8*1024+1,641024]     1024byte对⻬     freelist[128,184)
// [64*1024+1,256*1024]  8*1024byte对⻬   freelist[184,208)

//计算哈希映射关系的类
class SizeClass
{
public:
	//计算实际要申请的空间大小
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}
	//计算申请的空间应该在哈希桶的哪个位置
	static inline size_t Index(size_t size)
	{
		assert(size <= MAX_BYTES);
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_array[0] + group_array[1];
		}
		else if (size <= 64 * 1028)
		{
			return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (size <= 256 * 1028)
		{
			return _Index(size - 64 * 1028, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
	}


	//static inline size_t _RoundUp(size_t size, size_t alignNum)  //参数：申请的空间大小，对齐数
	//{
	//	size_t alignSize = size;
	//	if (size % alignNum != 0)
	//		alignSize = ( size / alignNum + 1 ) * alignNum;
	//	return alignSize;
	//} 

	//使用位运算会比加减乘除效率高一些，毕竟我们实现的是高性能的项目
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1)); 
	}
	
	//static inline size_t _Index(size_t size, size_t alignNum)
	//{
	//	if (size % alignNum == 0)
	//	{
	//		return size / alignNum - 1;
	//	}
	//	else
	//	{
	//		return size / (2 << alignNum);
	//	}
	//}

	static inline size_t _Index(size_t size, size_t align_shift)
	{
		return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
	}
};


//管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0;          //大块内存起始的页号
	size_t _n = 0;                //页的数量
	size_t _useCount = 0;         //切好的小块内存，被分配给thread cache的数量
	void* _freeList = nullptr;    //连接切好但没有分配的内存的自由链表
	size_t _objSize = 0;          //切好的小对象的大小

	bool _isUse = false;          //是否在被使用

	Span* _next = nullptr;
	Span* _prev = nullptr;
};

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;

		newSpan->_prev = prev;
		newSpan->_next = pos;
		prev->_next = newSpan;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		//条件断点，查看栈帧
		/*if (pos == _head)
		{
			int x = 0;
		}*/

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	std::mutex& GetMtx()
	{
		return _mtx;
	}

private:
	Span* _head;       //哨兵位头节点
	std::mutex _mtx;   //桶锁
};

class UnitClass
{
public:
	//一次thread cache从中心缓存中获取多少个相同容量空间
	static inline size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		int num = MAX_BYTES / size;
		//让获取的个数保持在[2, 512]之间
		//小对象多给一些，最多512个
		//大对象少给一些，最少2个
		if (num < 2) num = 2;
		else if (num > 512) num = 512;

		return num;
	}

	//计算CentralCache一次向系统获取几个页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if(npage == 0)
			npage = 1;

		return npage;
	}
};